--[[ 
A simple library for processing tables in a list-like fashion. Includes the primitives of 
functional programming filter, map, and reduce. 

The list table is meant to be used both as a class and as a namespace for list-related functions. 
All functions in list can be passed a regular table as argument. 
--]]
module(..., package.seeall)


list = class("list")
_G.list = list

list.insert = table.insert
list.pop    = table.remove
list.sort   = table.sort
list.concat = table.concat

function list.__new(self, ...)
    return {...}
end

function list.__index(self, key)
	if type(key) == "number" and math.isinteger(key) and -#self <= key and key <= -1 then
		return self[key + #self + 1]
	end
	return getmetatable(self)[key]
end

function list.__tostring(self)
    local elems = list("[")
    for _, v in ipairs(self) do
        elems:append(tostring(v))
        elems:append(", ")
    end
    if #self > 0 then
        elems:pop()
    end
    elems:append("]")
    return elems:concat()
end
list.repr = list.__tostring

function list.__iter(self)
    --[[ Iteration metamethod used by the iter() function in utils.misc. This iterator, unlike 
    ipairs(), returns only the list's elements. Note that ipairs() can still be used as, other 
    than having list as its metatable, a list is still a regular lua table. ]]
    local i = 0
    return function()
        i = i + 1
        return (i <= #self) and self[i] or nil
    end
end
list.iter = list.__iter

function list.clear(self)
    for i = 1, #self do self[i] = nil end
end

function list.copy(self, target)
    --[[ Copies the list part of self into target, or into a new empty list if a target is not 
    provided. ]]
    target = target or list()
    for i, v in ipairs(self) do target[i] = v end
    return target
end

function list.append(self, v)
    --[[ Append a value to the end of list. ]]
    self[#self + 1] = v
end

function list.extend(self, other)
    --[[ Extend a list with the contents of another list. ]]
    for _, v in ipairs(other) do self[#self + 1] = v end
end

function list.index(self, v)
    --[[ Given a value, returns the integer key associated to that value. ]]
    for i, u in ipairs(self) do
        if u == v then 
            return i 
        end
    end
    error("value not found in list")
end

function list.remove(self, v)
    --[[ Remove a value from a list, shifting down all elements after it. ]]
    return list.pop(self, list.index(self, v))
end

function list.reverse(self, other)
    --[[ Reverse list 'self' into list 'other' (or operate in-place if other is not provided). ]]
    other = other or self
    local n = #self
    for i = 1, math.floor(n / 2) do
        -- use two simultaneous assignments to make the 
        -- function work even when operating in-place
        other[i], other[n-i+1] = self[n-i+1], self[i]
    end
    return other
end

function list.reversed(self)
    --[[ Returns a reversed copy of this list. ]]
    return list.reverse(self, list())
end

function list.is_sorted(self, reverse)
    --[[ Check if the list is sorted. If reverse is true, then the function returns true if the 
    list's elements are in decreasing order. ]]
    local reverse = reverse or false
    local prev = self[1]
    for i = 2, #self do
        local curr = self[i]
        if (not reverse and prev > curr) or (reverse and prev < curr) then
            return false
        end
        prev = curr
    end
    return true
end

function list.bisect_right(self, v, lo, hi)
    --[[ Assuming 'self' is a sorted list, compute the index where 'v' should be inserted in 
    'self', such that 'self' continues to be sorted. The slice in 'self' where the binary search 
    is performed may be limited with the 'lo' and 'hi' indices. The index is computed in such a 
    way that 'v' will appear to the right (hence the name bisect_right) of elements with the same 
    value. ]]
    if #self == 0 then return 1 end
    lo = lo or 1
    hi = hi or (#self + 1)
    repeat
        local i = math.floor((lo + hi) / 2)
        if v >= self[i] then
            lo = i + 1
        else
            hi = i
        end
    until lo == hi
    return lo
end

function list.bisect_left(self, v, lo, hi)
    --[[ Same as bisect_right(), but the insertion index is computed such that 'v' appears to the 
    left of elements with the same value. ]]
    if #self == 0 then return 1 end
    lo = lo or 1
    hi = hi or (#self + 1)
    repeat
        local i = math.floor((lo + hi) / 2)
        if v > self[i] then
            lo = i + 1
        else
            hi = i
        end
    until lo == hi
    return lo
end

function list.insort_right(self, v, lo, hi)
    local i = list.bisect_right(self, v, lo, hi)
    list.insert(self, i, v)
end

function list.insort_left(self, v, lo, hi)
    local i = list.bisect_left(self, v, lo, hi)
    list.insert(self, i, v)
end

list.bisect = list.bisect_right
list.insort = list.insort_right

function list.map(self, func, other)
    --[[ Derive a new list 'other' by applying 'func' to the values in list 'self'. ]]
    other = other or list()
    for i, v in ipairs(self) do
        other[i] = func(v)
    end
    return other
end

function list.filter(self, func, other)
    --[[ Filter a list 'self' using 'func'. ]]
    other = other or list()
    for i, v in ipairs(self) do
        if func(v) then other[#other + 1] = v end
    end
    return other
end

function list.reduce(self, func, v0)
    --[[ Reduce a list 'self' to a single value using the operation specified by 'func'. ]]
    local i0 = 1
    if v0 == nil then
        v0 = self[1]
        i0 = 2
    end
    for i = i0, #self do
        v0 = func(v0, self[i])
    end
    return v0
end


--------------------------------------------------------------------------------
-- Test code
--------------------------------------------------------------------------------
local function log(...)
    io.write(string.format(...)) 
end

function test_bisect()
    log("testing list bisection functions... ")
    
    local self = list(1,2,3,4,5)
    assert(self:bisect_right(2) == 3)
    assert(self:bisect_left(2) == 2)
    assert(self:bisect_right(5) == 6)
    assert(self:bisect_right(1) == 2)
    assert(self:bisect_left(1) == 1)
    for i = 1, 100 do
        self:insort(1 + 4 * math.random())
        assert(self:is_sorted())
    end
    log("all tests passed.\n")
    return self
end

function test_functional()
    require "utils.table"
    
    log("testing functional programming primitives... ")
    local self = list(1,2,3,4,5)
    assert(table.equals(self:map(function(v) return v % 2 end), {1, 0, 1, 0, 1}))
    assert(table.equals(self:filter(function(v) return v % 2 == 0 end), {2, 4}))
    assert(table.equals(self:filter(function(v) return v % 2 == 1 end), {1, 3, 5}))
    assert(self:reduce(function(u, v) return u + v end) == 15)
    log("all tests passed.\n")
end

function test()
    test_bisect()
    test_functional()
end
